﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

using GameLibrary;

namespace UserInterface.Helpers.Graph
{
    [Serializable]
    public class Dijkstra_ShortPathAlgorithm_1959
    {
        private class Node : IComparable<Node>
        {
            public GraphNode GraphNode; // current position in graph
            public List<GraphNode> Path; // record a tree branch which can reach to it

            public double PathLength
            {
                get { return Path.Sum(n => n.Weight); }
            }

            public Node(GraphNode node)
            {
                this.GraphNode = node;
                this.Path = new List<GraphNode> { node };
            }

            public Node(GraphNode node, Node parentNode)
            {
                this.GraphNode = node;
                this.Path = new List<GraphNode>(parentNode.Path);
                this.Path.Add(node);
            }

            public GraphNode SecondLastGrapnNode
            {
                get
                {
                    int _2ndLastPosition = Path.Count - 2;
                    if (_2ndLastPosition >= 0)
                        return Path[_2ndLastPosition];
                    else
                        return Path[0];
                }
            }

            #region IComparable<Node> Members

            public int CompareTo(Node other)
            {
                return this.PathLength.CompareTo(other.PathLength);
            }

            #endregion
        }

        private HashSet<Node> BranchesSelected;
        private HashSet<Node> BranchesInConsideration;
        private HashSet<GraphNode> SelectedGraphNode;
        private HashSet<GraphNode> RemainingGraphNode;

        private Graph Map;
        private GraphNode From;
        private double? MaxLength;

        public Dijkstra_ShortPathAlgorithm_1959(Graph map, GraphNode from, double? maxLength)
        {
            this.Map = map;
            this.From = from;

            this.BranchesSelected = new HashSet<Node>();
            this.BranchesInConsideration = new HashSet<Node>();

            this.SelectedGraphNode = new HashSet<GraphNode>();
            this.RemainingGraphNode = new HashSet<GraphNode>();
            this.RemainingGraphNode.AddRange(map.GraphNodes);

            this.MaxLength = maxLength;
        }

        public Graph GetResult()
        {
            this.Init();

            do
            {
                var selectedNode = this.Step_1();
                this.Step_2(selectedNode);
            } while (this.BranchesInConsideration.Count > 0) ;

           return this.CreateTreeFromBranchesSelected(this.MaxLength);
        }

        private void Init()
        {
            Node node = this.GetNodeFromGraphNode(this.From);
            this.AddNodeToBrahcnesInConsideration(node);           
        }

        private Node Step_1()
        {
            Node nodeWithShortestBranch = this.SelectNodeWithShortestBranchFromBrahcnesInConsideration();
            this.RemoveNodeFromBranchesInConsideration(nodeWithShortestBranch);
            this.AddNodeToBranchesSelected(nodeWithShortestBranch);
            this.AddGraphNodeToSelectedGraphNodes(nodeWithShortestBranch);
            this.RemoveGraphNodeFromRemainingGraphNodes(nodeWithShortestBranch);
            return nodeWithShortestBranch;
        }

        private void Step_2(Node selectedNode)
        {
            var branches =
                 this.FindBranchesOfSelectedNodeInRemainingGraphNodes(selectedNode);
            this.ReplaceNodesInBranchesInConsiderationIfItsPathLongerThanBranches(
                                                branches, 
                                                selectedNode);            
        }

        private Node GetNodeFromGraphNode(GraphNode graphNode, Node parentNode = null)
        {
            if (parentNode != null)
                return new Node(graphNode, parentNode);
            else
                return new Node(graphNode);
        }

        private void AddNodeToBranchesSelected(Node node)
        {
            this.BranchesSelected.Add(node);
        }

        private void AddNodeToBrahcnesInConsideration(Node node)
        {
            this.BranchesInConsideration.Add(node);
        }

        private Node SelectNodeWithShortestBranchFromBrahcnesInConsideration()
        {
            var list = this.BranchesInConsideration.ToList();
            list.Sort();
            return list.First();
        }

        private void RemoveNodeFromBranchesInConsideration(Node node)
        {
            this.BranchesInConsideration.Remove(node);
        }

        private void RemoveGraphNodeFromRemainingGraphNodes(Node node)
        {
            this.RemainingGraphNode.Remove(node.GraphNode);
        }

        private void AddGraphNodeToSelectedGraphNodes(Node node)
        {
            this.SelectedGraphNode.Add(node.GraphNode);
        }

        private IEnumerable<GraphNode> 
            FindBranchesOfSelectedNodeInRemainingGraphNodes(
            Node node)
        {
            HashSet<GraphNode> neighbors = new HashSet<GraphNode>(
                                            this.Map.GetNeighborsOfOneNode(
                                                                node.GraphNode
                                                                        )
                                                                );

            return from ng in this.RemainingGraphNode
                   where neighbors.Contains(ng)
                   select ng;
        }

        private void ReplaceNodesInBranchesInConsiderationIfItsPathLongerThanBranches(
            IEnumerable<GraphNode> nodes, 
            Node selectedNode)
        {
            var nodesInSetII 
                = this.GetNodesWithSameGraphNodeInBranchesInConsideration(nodes);


            foreach (Node n in nodesInSetII)
            {
                var node = this.GetNodeFromGraphNode(n.GraphNode, selectedNode);
                if (this.ExistingNodeHaveLongerPath(n, node))
                {
                    this.RemoveNodeFromBranchesInConsideration(n);// reject old node                    
                    this.AddNodeToBrahcnesInConsideration(node);
                }
                // else new node is rejected
            }

            var nodesNotInBranchesInConsideration = this.GetGraphNodesNotInBranchesInConsideration(nodes);

            foreach (GraphNode gn in nodesNotInBranchesInConsideration)
            {
                var node = this.GetNodeFromGraphNode(gn, selectedNode);
                this.AddNodeToBrahcnesInConsideration(node);
            }
        }

        private IEnumerable<GraphNode> GetGraphNodesNotInBranchesInConsideration(
            IEnumerable<GraphNode> nodes)
        {
            HashSet<GraphNode> setIINodes = new HashSet<GraphNode>(from n in this.BranchesInConsideration
                                                                   select n.GraphNode);
            return from n in nodes
                   where setIINodes.Contains(n) == false
                   select n;
        }

        private IEnumerable<Node> GetNodesWithSameGraphNodeInBranchesInConsideration(
            IEnumerable<GraphNode> graphNodes)
        {
            HashSet<GraphNode> neighbors = new HashSet<GraphNode>(graphNodes);
            return from node in BranchesInConsideration
                   where neighbors.Contains(node.GraphNode)
                   select node;
        }

        private bool ExistingNodeHaveLongerPath(Node existingNode, Node newNode)
        {
            return existingNode.PathLength > newNode.PathLength;
        }

        private Graph CreateTreeFromBranchesSelected(double? maxLength = null)
        {
            if (maxLength.HasValue == false)
                return this.CreateGraphWithNoLengthLimit();
            else
                return this.CreateGraphWithLengthLimit(maxLength.Value);
        }

        private Graph CreateGraphWithNoLengthLimit()
        {
            Graph graph = new Graph();
            foreach (Node node in this.BranchesSelected)
            {
                graph.AddNode(node.GraphNode);
                graph.AddNeighborsOfOneNode(node.GraphNode, 
                                            new List<GraphNode> { node.SecondLastGrapnNode });
            }
            return graph;
        }

        private Graph CreateGraphWithLengthLimit(double maxLength)
        {
            Graph graph = new Graph();
            foreach (Node node in this.BranchesSelected)
            {
                if (node.PathLength <= (maxLength + From.Weight))
                {
                    graph.AddNode(node.GraphNode);
                    graph.AddNeighborsOfOneNode(node.GraphNode, new List<GraphNode> { node.SecondLastGrapnNode });
                }
            }
            return graph;
        }
    }
}
